package tree;

import java.util.prefs.NodeChangeEvent;

/**
 * 二叉树线索化
 * 二叉树线索化遍历
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode i1 = new HeroNode(1,"d");
        HeroNode i2 = new HeroNode(2,"dd");
        HeroNode i3 = new HeroNode(3,"ddd");
        HeroNode i4 = new HeroNode(4,"dddd");
        HeroNode i5 = new HeroNode(5,"ddddd");
        HeroNode i6 = new HeroNode(6,"dddddd");
        HeroNode i7 = new HeroNode(7,"ddddddd");
        HeroNode i8 = new HeroNode(8,"ddddddd");
        HeroNode i9 = new HeroNode(9,"ddddddd");
        HeroNode i10 = new HeroNode(10,"ddddddd");
        i1.setLeft(i2);
        i2.parent=i1;
        i1.setRight(i3);
        i3.parent=i1;
        i2.setLeft(i4);
        i4.parent=i2;
        i2.setRight(i5);
        i5.parent=i2;
        i3.setLeft(i6);
        i6.parent=i3;
        i3.setRight(i7);
        i7.parent=i3;
        i4.left=i8;
        i8.parent=i4;
        i4.right=i9;
        i9.parent=i4;
        i5.left=i10;
        i10.parent=i5;
        ThreadedBinaryTree b = new ThreadedBinaryTree();
        b.setRoot(i1);
        b.ThreadedproNodes();
        b.ThreadedpostList(i1);


    }
}
class ThreadedBinaryTree{
    HeroNode root;
    HeroNode pre =null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //前序线索化遍历
    public void ThreadedpreList(HeroNode root){
        HeroNode node = root;
        while(node!=null){
            System.out.println(node);
            while(node.leftType==0){
                node=node.left;
                System.out.println(node);
            }
            if(node.rightType==1){
                node=node.right.right;
                System.out.println(node);
            }
            if(node.right==null)
                return;
            node=node.right.right;

        }
    }
    //中序线索化遍历
    public void ThreadedinfixList(HeroNode root){
        HeroNode node = root;
        while(node!=null){
        while(node.leftType==0)
            node=node.left;
        System.out.println(node);
        if(node.rightType==1){
            node=node.right;
            System.out.println(node);
        }
        node=node.right;}
    }
    void postThreadList(HeroNode root) {
        //1、找后序遍历方式开始的节点
        HeroNode node = root;
        while(node != null && node.leftType==0) {
            node = node.left;
        }

        HeroNode preNode = null;
        while(node != null) {
            //右节点是线索
            if(node.rightType==1) {
                System.out.println(node + ", ");
                preNode = node;
                node = node.right;

            } else {
                //如果上个处理的节点是当前节点的右节点
                if(node.right == preNode) {
                    System.out.println(node+ ", ");
                    if(node == root) {
                        return;
                    }

                    preNode = node;
                    node = node.parent;

                } else {    //如果从左节点的进入则找到有子树的最左节点
                    node = node.right;
                    while(node != null && node.leftType==0) {
                        node = node.left;
                    }
                }
            }
        }
    }
    //后序线索化遍历
    public void ThreadedpostList(HeroNode root){
        HeroNode node = root;
        //判断此节点是否为线索化则
        while (node.left!=null&&node.leftType!=1){
            node=node.left;
        }
   HeroNode pre=null;
        while (node!=null){
            if(node.rightType==1){//如果是线索化
                System.out.println(node);
                pre=node;
                node=node.right;
            }else {
                if(node.right==pre){
                    System.out.println(node);
                    if(node==root){
                        return;
                    }
                    pre=node;
                    node=node.parent;
                }else {
                    node=node.right;
                    while (node.left!=null&&node.leftType!=1){
                        node=node.left;
                    }
                }
            }
        }
        }
       /* while(node!=null){
            while(node.leftType==0){
                node=node.left;
                System.out.println(node);
            }
             if (node.rightType==1){
                 System.out.println(node.right);
                 node=node.right;

             }
        }
        System.out.println(root);*/
    //前序排序
    public void ThreadedpostNode(){
        ThreadedpostNode(root);
    }
    //前序排序
    private void ThreadedpostNode(HeroNode node){
        if(node.left==null){
            node.left=pre;
            node.leftType=1;
        }
        if(pre!=null&&pre.right==null){
            pre.right=node;
            pre.rightType=1;
        }
        pre=node;
        if(node.left!=null&&node.leftType!=1){
            ThreadedpostNode(node.left);
        }
        if(node.right!=null){
            ThreadedpostNode(node.right);
        }

    }
    //中序线索化
    public void ThreadedNodes(){
        ThreadedNodes(root);
    }
    //中序线索化
    private void ThreadedNodes(HeroNode node){
        if(node==null){
            return;
        }
        ThreadedNodes(node.left);
        if(node.left==null){
            node.left=pre;
            node.setLeftType(1);
        }
        if(pre!=null && pre.right==null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre=node;
        ThreadedNodes(node.right);
    }
    //后序排序
    public void ThreadedproNodes(){
        ThreadedproNodes(root);
    }
    //后序排序
    private void ThreadedproNodes(HeroNode node){
        if(node.left!=null){
            ThreadedproNodes(node.left);
        }
        if(node.right!=null){
            ThreadedproNodes(node.right);
        }
        if(node.left==null){
            node.left=pre;
            node.leftType=1;
        }
        if(pre!=null&&pre.right==null){
            pre.right=node;
            pre.rightType=1;
        }
        pre=node;
    }
}